Search Results

Documents authored by Stauffer, Alexandre

Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.39
Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents

Authors: Peter Gracar and Alexandre Stauffer

Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)

Abstract
We consider the problem of spread of information among mobile agents on the torus. The agents are initially distributed as a Poisson point process on the torus, and move as independent simple random walks. Two agents can share information whenever they are at the same vertex of the torus. We study the so-called flooding time: the amount of time it takes for information to be known by all agents. We establish a tight upper bound on the flooding time, and introduce a technique which we believe can be applicable to analyze other processes involving mobile agents.
Cite as

Peter Gracar and Alexandre Stauffer. Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gracar_et_al:LIPIcs.APPROX-RANDOM.2018.39,
  author =	{Gracar, Peter and Stauffer, Alexandre},
  title =	{{Percolation of Lipschitz Surface and Tight Bounds on the Spread of Information Among Mobile Agents}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.39},
  URN =		{urn:nbn:de:0030-drops-94439},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.39},
  annote =	{Keywords: Lipschitz surface, spread of information, flooding time, moving agents}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2017.34
Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings

Authors: Sarah Cannon, David A. Levin, and Alexandre Stauffer

Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)

Abstract
We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall, and Spencer in 2002. A dyadic tiling of size n is a tiling of the unit square by n non-overlapping dyadic rectangles, each of area 1/n, where a dyadic rectangle is any rectangle that can be written in the form [a2^{-s}, (a+1)2^{-s}] x [b2^{-t}, (b+1)2^{-t}] for a,b,s,t nonnegative integers. The edge-flip Markov chain selects a random edge of the tiling and replaces it with its perpendicular bisector if doing so yields a valid dyadic tiling. Specifically, we show that the relaxation time of the edge-flip Markov chain for dyadic tilings is at most O(n^{4.09}), which implies that the mixing time is at most O(n^{5.09}). We complement this by showing that the relaxation time is at least Omega(n^{1.38}), improving upon the previously best lower bound of Omega(n*log n) coming from the diameter of the chain.
Cite as

Sarah Cannon, David A. Levin, and Alexandre Stauffer. Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 34:1-34:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{cannon_et_al:LIPIcs.APPROX-RANDOM.2017.34,
  author =	{Cannon, Sarah and Levin, David A. and Stauffer, Alexandre},
  title =	{{Polynomial Mixing of the Edge-Flip Markov Chain for Unbiased Dyadic Tilings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)},
  pages =	{34:1--34:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-044-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{81},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.34},
  URN =		{urn:nbn:de:0030-drops-75830},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2017.34},
  annote =	{Keywords: Random dyadic tilings, spectral gap, rapid mixing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.187
Balls into bins via local search: cover time and maximum load

Authors: Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, and He Sun

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We study a natural process for allocating m balls into n bins that are organized as the vertices of an undirected graph G. Balls arrive one at a time. When a ball arrives, it first chooses a vertex u in G uniformly at random. Then the ball performs a local search in G starting from u until it reaches a vertex with local minimum load, where the ball is finally placed on. Then the next ball arrives and this procedure is repeated. For the case m=n, we give an upper bound for the maximum load on graphs with bounded degrees. We also propose the study of the cover time of this process, which is defined as the smallest m so that every bin has at least one ball allocated to it. We establish an upper bound for the cover time on graphs with bounded degrees. Our bounds for the maximum load and the cover time are tight when the graph is vertex transitive or sufficiently homogeneous. We also give upper bounds for the maximum load when m>=n.
Cite as

Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, and He Sun. Balls into bins via local search: cover time and maximum load. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 187-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.STACS.2014.187,
  author =	{Bringmann, Karl and Sauerwald, Thomas and Stauffer, Alexandre and Sun, He},
  title =	{{Balls into bins via local search: cover time and maximum load}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{187--198},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.187},
  URN =		{urn:nbn:de:0030-drops-44570},
  doi =		{10.4230/LIPIcs.STACS.2014.187},
  annote =	{Keywords: Balls and Bins, Stochastic Process, Randomized Algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact